package datastructure;

/**
 * Created with IntelliJ IDEA.
 * Description:
 *
 * @author lzy
 * @create 2019-11-12 下午12:07
 */
public class CalculateGCD {
    /**
     * 获取两个整数的最大公约数
     * 两个正整数a和ｂ（ａ>ｂ），他们的最大公约数等于ａ除以ｂ的余数ｃ和ｂ之间的最大公约数
     *
     * @param a
     * @param b
     * @return
     */
    public static int getGreatestCommonDivisor(int a, int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        if (big % small == 0) {
            return small;
        }
        return getGreatestCommonDivisor(big % small, small);
    }

    /**
     * 获取两个整数的最大公约数
     * 两个整数a和ｂ(a>b)，他们的最大公约数等于ａ-b的差值ｃ和较小数ｂ的最大公约数
     *
     * @param a
     * @param b
     * @return
     */
    public static int getGreatestCommonDivisorV2(int a, int b) {
        if (a == b) {
            return a;
        }
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        return getGreatestCommonDivisorV2(big - small, small);
    }

    /**
     * 经过优化后的方法
     * 更相减损术与移位相结合
     *
     * @param a
     * @param b
     * @return
     */
    public static int gcd(int a, int b) {
        if (a == b) {
            return a;
        }

        if ((a & 1) == 0 && (b & 1) == 0) {
            return gcd(a >> 1, b >> 1) << 1;
        } else if ((a & 1) == 0 && (b & 1) != 0) {
            return gcd(a >> 1, b);
        } else if ((a & 1) != 0 && (b & 1) == 0) {
            return gcd(a, b >> 1);
        } else {
            int big = a > b ? a : b;
            int small = a < b ? a : b;
            return gcd(big - small, small);
        }
    }

    public static void main(String[] args) {
        System.out.println(gcd(25, 5));
        System.out.println(gcd(100, 80));
        System.out.println(gcd(27, 14));
    }
}
